P2522 [HAOI2011]Problem b

显然，此题可用容斥化简：

$\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)=k]$

$\Rightarrow\sum_{i=1}^b\sum_{j=1}^d[gcd(i,j)=k]-\sum_{i=1}^{a-1}\sum_{j=1}^d[gcd(i,j)=k]-\sum_{i=1}^b\sum_{j=1}^{c-1}[gcd(i,j)=k]+\sum_{i=1}^{a-1}\sum_{j=1}^{c-1}[gcd(i,j)=k]$

对于每一部分，我们可以单独计算：

$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$

$\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[gcd(i,j)=1]$

$\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|gcd(i,j)}\mu(d)$

$\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor }\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}$

$\sum_{d=1}^{min(n,m)}\mu(d)\lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor$

可以用数论分块$\Theta(\sqrt{n}~)$解决，总复杂度为$\Theta(t\sqrt{n})$。

注意，这道题 #$define~int~~~long~long$会见祖宗的，答案开$long ~long$即可。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 50000;
int n , a , b , c , d , f[ MAXN + 5 ];

int mu[ MAXN + 5 ] , prime[ MAXN + 5 ] , k;
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
	for( int i = 1 ; i <= MAXN ; i ++ )
		f[ i ] = f[ i - 1 ] + mu[ i ];
}

long long solve( int n , int m ) {
	int d = min( n , m );
	long long Ans = 0;
	for( int l = 1 , r ; l <= d ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans = Ans + 1ll * ( f[ r ] - f[ l - 1 ] ) * ( n / k / l ) * ( m / k / l );
	}
	return Ans;
}
long long Get( ) {
	return solve( b , d ) - solve( a - 1 , d ) - solve( b , c - 1 ) + solve( a - 1 , c - 1 );
}

signed main( ) {
	sieve( ); 
	scanf("%d",&n);
	while( n -- ) {
		scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
		printf("%lld\n",Get( )); 
	} 
	return 0;
}